#include "headfiles.h"

static void queenCountRecur(int n, int index, 
                     int &output, bool *column, 
                     bool *ldiag, bool *rdiag) {
    if (index == n) {
        ++output;
        return;
    }

    int i;
    for (i = 0; i < n; i++) {
        if (column[i]) continue;
        if (ldiag[index + i]) continue;
        if (rdiag[index - i + n]) continue;

        column[i] = true;
        ldiag[index + i] = true;
        rdiag[index - i + n] = true;

        queenCountRecur(n, index + 1, output, column, ldiag, rdiag);

        column[i] = false;
        ldiag[index + i] = false;
        rdiag[index - i + n] = false;
    }

    return;
}

int queenCount(int n) {
    bool column[n] = {false};
    bool ldiag[2 * n] = {false};
    bool rdiag[2 * n] = {false};

    int output = 0;
    queenCountRecur(n, 0, output, column, ldiag, rdiag);

    return output;
}


